﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>
// 原题连接：https://leetcode.cn/problems/check-if-n-and-its-double-exist/
/*
题目描述：
给你一个整数数组 arr，请你检查是否存在两个整数 N 和 M，满足 N 是 M 的两倍（即，N = 2 * M）。
更正式地，检查是否存在两个下标 i 和 j 满足：
	i != j
	0 <= i, j < arr.length
	arr[i] == 2 * arr[j]

示例 1：
输入：arr = [10,2,5,3]
输出：true
解释：N = 10 是 M = 5 的两倍，即 10 = 2 * 5 。

示例 2：
输入：arr = [7,1,14,11]
输出：true
解释：N = 14 是 M = 7 的两倍，即 14 = 2 * 7 。

示例 3：
输入：arr = [3,1,7,11]
输出：false
解释：在该情况下不存在 N 和 M 满足 N = 2 * M 。
 

提示：
2 <= arr.length <= 500
-10^3 <= arr[i] <= 10^3
*/

// 方法1——暴力法
/*
思路：
直接遍历数组中的每个元素，对于每一个元素，都在遍历一次数组中除自身之外的所有元素
看看是否有刚好是自己两倍的元素。
若有，就直接返回true，若没有则继续遍历下一个元素。
如果所有元素都遍历完了也没有找到，就返回false
*/

// 有了以上思路，那我们写起代码来也就水到渠成了：
bool checkIfExist1(int* arr, int arrSize) {
	assert(arr);
	int i = 0;
	int j = 0;
	for (i = 0; i < arrSize; i++) {
		for (j = 0; j < arrSize; j++) {
			if (j == i) {
				continue;
			}
			if (arr[j] == 2 * arr[i]) {
				return true;
			}
		}
	}
	return false;
}
// 时间复杂度：O(n^2)，n为数组长度。
// 空间复杂度：O(1)。

// 方法2——排序后双指针
/*
思路：
在对数组进行排序之后，我们可以使用双指针来对数组进行遍历，
我们使用指针p来遍历数组的每一个元素，使用指针q来寻找与p所指向的元素的两倍相同的元素，具体做法如下：
判断大于或等于0的元素时，我们从前往后遍历，先让p一直向后移动，找到第一个大于或等于0的元素，
如果arr[p] == 0，则可以直接判断arr[p + 1]是否等于0，则直接返回true如果不等于，就让p++；
如果arr[p] > 0，则让指针q从p + 1位置开始遍历后面元素，如果发现arr[q] = 2 * arr[p]，则直接返回true，
如果发现arr[q] > 2 * arr[p]，则说明2 * arr[p]在数组中已不可能出现，则跳出循环，让p++，因为在指针p不断往后走的同时
arr[p]值也在不断增加，当然2 * arr[p]的值也在不断增加，所以指针q可以原地不动。

判断小于0的元素时，我们从后往前遍历，先让p一直往移动，找到第一个小于0的元素，
此时让指针q从p的前一个位置开始，遍历数组剩下的元素，如果出现arr[q] == 2 * arr[p]，则直接返回true，
如果发现arr[q] < 2 * arr[p]，则说明2 * arr[p]在数组中已不可能出现，则跳出循环，让p--，因为在指针p不断向前移动的同时
arr[p]也在不断地减小，当然2 * arr[p]也在不断的减小，所以指针q也可以原地不动。
*/

// 有了以上思路，那我们写起代码来也就水到渠成了：
// 先写一个函数，比较两个整型数据的大小
int cmp_int(const void* p1, const void* p2) {
	assert(p1 && p2);
	return *((int*)p1) - *((int*)p2);
}
bool checkIfExist2(int* arr, int arrSize) {
	assert(arr);
	int p = 0;
	int q = 0;
	// 先对数组进行排序
	qsort(arr, arrSize, sizeof(int), cmp_int);
	// 先判断大于等于0的元素
	while (arr[p] < 0) {
		p++;
		if (p >= arrSize) {
			break;
		}
	}
	q = p + 1;
	while ((p < arrSize) && (q < arrSize)) {
		if (0 == arr[p]) {
			if (0 == arr[p + 1]) {
				return true;
			}
		}
		else {
			while (arr[q] < 2 * arr[p]) {
				q++;
				if (q >= arrSize) {
					break;
				}
			}
			if (q >= arrSize) {
				break;
			}
			if (arr[q] == 2 * arr[p]) {
				return true;
			}
		}
		p++;
	}
	// 再判断小于0的元素
	p = arrSize - 1;
	while (arr[p] >= 0) {
		p--;
		if (p < 0) {
			break;
		}
	}
	q = p - 1;
	while ((p >= 0) && (q >= 0)) {
		while (arr[q] > 2 * arr[p]) {
			q--;
			if (q < 0) {
				break;
			}
		}
		if (q < 0) {
			break;
		}
		if (arr[q] == 2 * arr[p]) {
			return true;
		}
		p--;
	}
	return false;
}
// 时间复杂度：O(nlogn)，其中n为数组长度，排序数组需要的时间复杂度为O(nlogn)，使用双指针遍历数组的时间复杂度为O(n)。
// 故总体时间复杂度为O(nlogn)。
// 空间复杂度：O(1)，我们只需要用到常数级的额外空间。


// 改进
/*
改进思路：
其实我们可以在一层循环就完成双指针的遍历。
在对数组进行排序后，用两个指针对数组进行遍历
先让一个指针p遍历数组的每一个元素，
当arr[p] > 0时，就使用q指针向后遍历，当出现arr[q] == 2 * arr[p]时，直接返回true即可，当出现arr[q] > 2 * arr[p]时候，
则说明数组中已不在可能2 * arr[p]，则让p后移一位，q保持原位。
当arr[p] < 0时，则需利用q指针向后遍历，当出现arr[q] == arr[p] / 2时，则直接返回true，当出现arr[q] > arr[p] / 2时候，
则说明数组中已不在可能arr[p] / 2，则让p后移一位，q保持原位。
*/

// 有了以上思路，那我们写起代码来也就水到渠成了：
bool checkIfExist3(int* arr, int arrSize) {
	assert(arr);
	int p = 0;
	int q = 0;
	// 先对数组进行排序
	qsort(arr, arrSize, sizeof(int), cmp_int);
	while ((p < arrSize) && (q < arrSize)) {
		if (arr[p] > 0) {
			while (arr[q] < 2 * arr[p]) {
				q++;
				if (q >= arrSize) {
					break;
				}
			}
			if (q >= arrSize) {
				break;
			}
			if (arr[q] == 2 * arr[p]) {
				return true;
			}
		}
		else if (arr[p] < 0) {
			while (arr[q] < arr[p] / 2.0) { // 要将arr[p] / 2 的运算转化成double型运算，防止向下取整所带来的数据不准确问题
				q++;
				if (q >= arrSize) {
					break;
				}
			}
			if (q >= arrSize) {
				break;
			}
			if (arr[q] == arr[p] / 2.0) {
				return true;
			}
		}
		else {
			if (0 == arr[p + 1]) {
				return true;
			}
		}
		p++;
	}
	return false;
}
// 时间复杂度：O(nlogn)，其中n为数组长度，排序数组需要的时间复杂度为O(nlogn)，使用双指针遍历数组的时间复杂度为O(n)。
// 故总体时间复杂度为O(nlogn)。
// 空间复杂度：O(1)，我们只需要用到常数级的额外空间。

int main() {
	int arr[] = { 102,-592,457,802,98,-132,883,356,-857,461,-453,522,250,476,991,540,-852,-485,-637,999,-803,-691,-880,881,-584,750,-124,745,-909,-892,304,-814,868,665,50,-40,26,-242,-797,-360,-918,-741,88,-933,-93,360,-738,833,-191,563,449,840,806,-87,-950,508,74,-448,-815,-488,639,-334 };
	int len = sizeof(arr) / sizeof(arr[0]);
	printf("%d\n", checkIfExist2(arr, len));


	return 0;
}